# -*- coding: utf-8 -*-
# Trabalho de Inteligência Artificial
# Semestre 2009.2
# Mineração de Dados
# Implementação do algoritmo ID3

import math
import orange

# Funções para a árvore de decisão

# Cria a lista de todos os valores para cada registro
# e retorna o valor que aparece mais vezes
def majority_value(data, target_attr):
    data = data[:]
    return most_frequent([record[target_attr] for record in data])

# Retorna o item mais frequente de uma lista
def most_frequent(lst):
    lst = lst[:]
    highest_freq = 0
    most_freq = None

    for val in unique(lst):
        if lst.count(val) > highest_freq:
            most_freq = val
            highest_freq = lst.count(val)
            
    return most_freq

# Remove itens duplicados na lista
def unique(lst):
    lst = lst[:]
    unique_lst = []

    for item in lst:
        if unique_lst.count(item) <= 0:
            unique_lst.append(item)
            
    return unique_lst

# Retorna uma lista de valores no atributo escolhido para
# cada registro e remove os redundantes
def get_values(data, attr):
    data = data[:]
    return unique([record[attr] for record in data])

# Retorna o atributo com maior ganho (ou menor entropia)
def choose_attribute(data, attributes, target_attr, fitness):
    data = data[:]
    best_gain = 0.0
    best_attr = None

    for attr in attributes:
        gain = fitness(data, attr, target_attr)
        if (gain >= best_gain and attr != target_attr):
            best_gain = gain
            best_attr = attr
                
    return best_attr

# Retorna uma lista de todos os registros com valor de atributo desejado
def get_examples(data, attr, value):
    data = data[:]
    rtn_lst = []
    
    if not data:
        return rtn_lst
    else:
        record = data.pop()
        if record[attr] == value:
            rtn_lst.append(record)
            rtn_lst.extend(get_examples(data, attr, value))
            return rtn_lst
        else:
            rtn_lst.extend(get_examples(data, attr, value))
            return rtn_lst

# Percorre a árvore de decisão e retorna uma classificação para dado registro
def get_classification(record, tree):
    # Se é uma string é porque é folha, então podemos retorná-lo
		if type(tree) == type("string"):
						return tree

    # Percorre a árvore até encontrar uma folha
		else:
				attr = tree.keys()[0]
				t = tree[attr][record[attr]]
				return get_classification(record, t)

# Retorna uma lista de classificações para cada um dos registros
# como determinado pela árvore de decisão
def classify(tree, data):
    data = data[:]
    classification = []
    
    for record in data:
        classification.append(get_classification(record, tree))

    return classification

# Retorna uma nova árvore de decisão
def create_decision_tree(data, attributes, target_attr, fitness_func):
    data = data[:]
    vals = [record[target_attr] for record in data]
    default = majority_value(data, target_attr)

		# Retorna o valor padrão se o dataset ou a lista de atributos são vazios
    if not data or (len(attributes) - 1) <= 0:
        return default
    
		# Retorna a classificação se todos tem a mesma classificação
    elif vals.count(vals[0]) == len(vals):
        return vals[0]
    else:
        # Escolhe o melhor atributo que melhor classifique os dados
        best = choose_attribute(data, attributes, target_attr,
                                fitness_func)

				# Cria uma árvore de decisão com o melhor atributo escolhido
        tree = {best:{}}

        for val in get_values(data, best):
            # Cria a subárvore
            subtree = create_decision_tree(
                get_examples(data, best, val),
                [attr for attr in attributes if attr != best],
                target_attr,
                fitness_func)

            tree[best][val] = subtree

    return tree

# Funções para o algoritmo ID3 (cálculo de entropia e ganho)

# Função para cálculo de entropia
def entropy(data, target_attr):
   
		# Inicializamos a frequência e a entropia
		val_freq = {}
		data_entropy = 0.0

    # Calcula a frequência de cada atributo
		for record in data:
			if (val_freq.has_key(record[target_attr])):
				val_freq[record[target_attr]] += 1.0
			else:
				val_freq[record[target_attr]] = 1.0

		# Calcula a entropia
		for freq in val_freq.values():
			data_entropy += (-freq/len(data)) * math.log(freq/len(data), 2) 
		
		return data_entropy

# Calcula o ganho
def gain(data, attr, target_attr):
    
		val_freq = {}
		subset_entropy = 0.0

    # Calcula a frequência
		for record in data:
			if (val_freq.has_key(record[attr])):
				val_freq[record[attr]] += 1.0
			else:
				val_freq[record[attr]] = 1.0

		# Calcula a soma da entropia para cada subconjunto de registros
		# baseando pela probabilidade de ocorrência no conjunto de treino
		for val in val_freq.keys():
			val_prob = val_freq[val] / sum(val_freq.values())
			data_subset = [record for record in data if record[attr] == val]
			subset_entropy += val_prob * entropy(data_subset, target_attr)

    # Retorna a diferença entre entropia do atributo escolhido e a do conjunto inteiro
		return (entropy(data, target_attr) - subset_entropy)

# Implementação do classificador no Orange

class Learner(object):
    def __new__(cls, examples=None, name="ID3", **kwds):
        learner = object.__new__(cls, **kwds)
        if examples:
            learner.__init__(name)
            return learner(examples)
        else:
            return learner

		# Define um nome para o classificador
    def __init__(self, name='ID3'):
        self.name = name

		# Chama o classificador
    def __call__(self, data):
        return Classifier(data)

class Classifier:
    def __init__(self, train, **kwds):
        self.__dict__ = kwds
        
				# Pré-processamento da entrada
        
        attributes = []
        for a in train.domain.attributes:
                attributes.append(a.name) 
        target_attr = train.domain.classVar.name
        self.classes = train.domain.classVar.values
        attributes.append(target_attr)
        data = []
        train_set = []
        k = 0
        for i in train:
                train_set.append([])
                for j in i:
				                train_set[k].append(j.value)
                k += 1
        for i in train_set:
                d = {}
                for j in range(len(attributes)):
                        a = attributes[j]
                        v = i[j]
                        d[a] = v
                data.append(d)
        self.tree = create_decision_tree(data, attributes, target_attr, gain)
        self.attributes = attributes


		# Realiza a classificação de fato
    def __call__(self, example, resultType = orange.GetValue):
        test = {}
        for i in range(len(example)):
                test[self.attributes[i]] = example[i].value
        classification = classify(self.tree, [test])
        
				# Retornamos 1 se acertou ou 0 se errou
        prob = []
        value = classification[0]
        for i in self.classes:
                if i == value:
								         prob.append(1)
                else:
                         prob.append(0)

        # Retorna o resultado no formato pedido
        if resultType == orange.GetValue: 
                return value
        elif resultType == orange.GetProbabilities: 
                return orange.DiscDistribution(prob)
        else: 
                return (value, orange.DiscDistribution(prob))
